/*
 * MinCoins.h
 *
 *  Created on: 2011-3-9
 *      Author:蓝达斌
 *
 *   Copyright   : Copyright © 2011 Binda&Aeolus
                   All Rights Reserved
 */

#ifndef MINCOINS_H_
#define MINCOINS_H_
class MinCoins
{
public:
	/*@param t :面值种类数组
	 *@param coins:面值的个数数组
	 *@param total:要换的面额
	 *@param 面值的种类数
	 *@return 最小的硬币数
	 */
	int  MakeChanges(int *t,int *coins,int total,int values)
	{
		int i, j, k;
		int c[11][20002];//c[i][j]前i种硬币找j块钱最少硬币数
       /* int mytotal;
		for(int x=0;x<values;x++)
		{
			 mytotal+=t[x]*coins[x];
		}
		if(total>mytotal) return -1;*/

			for (i = 1; i <= values; i++)
				//初始化
				for (j = 0; j <= total; j++) {
					if (j == 0)
						c[i][j] = 0;
				 	else if (i == 1)
						 if (j % t[i] == 0 && j / t[i] <= coins[i])//可以整除的
							c[1][j] = j / t[i];
						 else
							c[1][j] = 1000000;
					 else
						c[i][j] = 1000000;
				}

			    for (i = 2; i <= values; i++) //构造c数组
				  for (j = 1; j <= total; j++)
					for (k = 0; k <= coins[i]; k++) {
						if (c[i][j] > (c[i - 1][j - k * t[i]] + k) && (j - k * t[i])
								>= 0)
							c[i][j] = c[i - 1][j - k * t[i]] + k;
					}


			if (c[values][total]!= 1000000) {
				printf("%d values", c[values][total]); return c[values][total];
			} else
				printf(" -1 values");
			return -1;



	}

};

#endif /* MINCOINS_H_ */
